GATE Exam > GATE Questions > Consider the following language:L = {x ∈...
Start Learning for Free
Consider the following language:
L = {x ∈ {a, b}*⏐number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________.
L = {x ∈ {a, b}*⏐number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________.
Correct answer is '6'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
Consider the following language:L = {x ∈ {a, b}*number of a&rsquo...
The minimum number of states in a DFA that accepts:
L = { x ∈ {a, b }*⏐ number of a’s is divisible by 2 but not divisible by 3} is 6 states as shown below:
(or) alternatively it can be designed by taking a product automata of
L1 = {x ∈ {a, b }*⏐ number of a’s divisible by 2} and L2 = { x ∈ {a , b }*⏐ number of a’s not divisible by 3} as shown below:
Minimum DFA for L1:
Minimum DFA for L2:
Product automata L1 ∩ L2 having six states, shown below:
Which is same as our directly designed machine with 6 states.
L = { x ∈ {a, b }*⏐ number of a’s is divisible by 2 but not divisible by 3} is 6 states as shown below:
(or) alternatively it can be designed by taking a product automata of
L1 = {x ∈ {a, b }*⏐ number of a’s divisible by 2} and L2 = { x ∈ {a , b }*⏐ number of a’s not divisible by 3} as shown below:
Minimum DFA for L1:
Minimum DFA for L2:
Product automata L1 ∩ L2 having six states, shown below:
Which is same as our directly designed machine with 6 states.
Most Upvoted Answer
Consider the following language:L = {x ∈ {a, b}*number of a&rsquo...
The language L can be described as the set of all strings that start with one or more 0's followed by one or more 1's. In other words, L is the language of all binary strings that have at least one 0 followed by at least one 1.
For example, some strings in L are:
- 0101
- 000111
- 0011111
- 0000001111
On the other hand, some strings that are not in L are:
- 1111 (no 0's)
- 0000 (no 1's)
- 011 (not enough 1's)
Formally, L can be defined as:
L = {x | x starts with one or more 0's followed by one or more 1's}
or using regular expression notation:
L = {0+1+}
For example, some strings in L are:
- 0101
- 000111
- 0011111
- 0000001111
On the other hand, some strings that are not in L are:
- 1111 (no 0's)
- 0000 (no 1's)
- 011 (not enough 1's)
Formally, L can be defined as:
L = {x | x starts with one or more 0's followed by one or more 1's}
or using regular expression notation:
L = {0+1+}
|
Explore Courses for GATE exam
|
|
Similar GATE Doubts
Consider the following language:L = {x ∈ {a, b}*number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________.Correct answer is '6'. Can you explain this answer?
Question Description
Consider the following language:L = {x ∈ {a, b}*number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________.Correct answer is '6'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about Consider the following language:L = {x ∈ {a, b}*number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________.Correct answer is '6'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Consider the following language:L = {x ∈ {a, b}*number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________.Correct answer is '6'. Can you explain this answer?.
Consider the following language:L = {x ∈ {a, b}*number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________.Correct answer is '6'. Can you explain this answer? for GATE 2024 is part of GATE preparation. The Question and answers have been prepared according to the GATE exam syllabus. Information about Consider the following language:L = {x ∈ {a, b}*number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________.Correct answer is '6'. Can you explain this answer? covers all topics & solutions for GATE 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Consider the following language:L = {x ∈ {a, b}*number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________.Correct answer is '6'. Can you explain this answer?.
Solutions for Consider the following language:L = {x ∈ {a, b}*number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________.Correct answer is '6'. Can you explain this answer? in English & in Hindi are available as part of our courses for GATE.
Download more important topics, notes, lectures and mock test series for GATE Exam by signing up for free.
Here you can find the meaning of Consider the following language:L = {x ∈ {a, b}*number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________.Correct answer is '6'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
Consider the following language:L = {x ∈ {a, b}*number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________.Correct answer is '6'. Can you explain this answer?, a detailed solution for Consider the following language:L = {x ∈ {a, b}*number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________.Correct answer is '6'. Can you explain this answer? has been provided alongside types of Consider the following language:L = {x ∈ {a, b}*number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________.Correct answer is '6'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice Consider the following language:L = {x ∈ {a, b}*number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ________.Correct answer is '6'. Can you explain this answer? tests, examples and also practice GATE tests.
|
|
Explore Courses for GATE exam
|
|
Suggested Free Tests
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup